/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Mar 24, 2014
 */
package zhoujian.oj.leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @version 1.0
 * @description Merge two sorted linked lists and return it as a new list. The
 *              new list should be made by splicing together the nodes of the
 *              first two lists.
 */
public class MergeTwoSortedLists {

	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		if (l1 == null) return l2;
		if (l2 == null) return l1;
		ListNode tmp;
		ListNode head = l1;
		if (l1.val > l2.val) {
			head = l2;
			l2 = l1;
			l1 = head;
		}
		
		while (l1.next != null && l2 != null) {
			if (l1.next.val <= l2.val)
				l1 = l1.next;
			else {
				tmp = l2;
				l2 = l2.next;
				tmp.next = l1.next;
				l1.next = tmp;
				l1 = tmp;
			}
		}
		
		if (l2 != null)
			l1.next = l2;
		
		return head;
	}
	
	// using comparator, can merge any number of lists
	public ListNode mergeUseQueue(ListNode l1, ListNode l2) {
		if (l1 == null) return l2;
		if (l2 == null) return l1;
		
		Comparator<ListNode> comparator = new Comparator<ListNode>() {
			
			@Override
			public int compare(ListNode o1, ListNode o2) {
				if (o1.val < o2.val)
					return -1;
				if (o1.val > o2.val)
					return 1;
				return 0;
			}
		};
		
		PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(2, comparator);
		queue.add(l1);
		queue.add(l2);
		
		ListNode head = queue.poll();
		ListNode cur = head;
		if (cur.next != null)
			queue.add(cur.next);
		while (!queue.isEmpty()) {
			cur.next = queue.poll();
			cur = cur.next;
			if (cur.next != null)
				queue.add(cur.next);
		}
		
		return head;
	}
}
